/**
 * Copyright 厦门中软海晟信息技术有限公司 版权所有 违者必究 2019
 */
package com.vijos;

/**
 * @author : sunzb(sunzb@hsit.com.cn)
 * @date: 2019/4/25
 */
// 康托展开
public class KangTuo {

    public static final int FAC[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};    // 阶乘

    public static int cantor(int[] a) {
        int length = a.length;
        int x = 0;
        for (int i = 0; i < length; ++i) {
            int smaller = 0;  // 在当前位之后小于其的个数
            for (int j = i + 1; j < length; ++j) {
                if (a[j] < a[i])
                    smaller++;
            }
            x += FAC[length - i - 1] * smaller; // 康托展开累加
        }
        return x;  // 康托展开值
    }

    public static void main(String[] args) {
        System.out.println(cantor(new int[] {2, 3, 1}));
    }
}
